/**
 * 
 */
package hihocoder;

/**
 * @author zhong
 *
 */
public class CouplesHoldingHands {
	public int minSwapsCouples(int[] row) {
		int n = row.length;
		int[] indexes = new int[n];// 记录每个元素所在位置
		for (int i = 0; i < n; i++) {
			indexes[row[i]] = i;
		}
		int ans = 0;
		boolean[] visited = new boolean[n];
		for (int i = 0; i < n; i++) {
			if (visited[i])
				continue;
			// 从i开始遍历
			ans += (DFS(i, row, indexes, visited) >> 1) - 1;
		}
		return ans;
	}

	private int DFS(int i, int[] row, int[] indexes, boolean[] visited) {
		if (visited[i]) {
			return 0;
		}
		visited[i] = true;
		int count = 1;
		// 邻居
		count += DFS((i & 1) == 0 ? i + 1 : i - 1, row, indexes, visited);
		// 对象以及对象的邻居
		int val = row[i];
		int love = (val & 1) == 0 ? val + 1 : val - 1;
		love = indexes[love];// 爱人所在位置
		count += DFS(love, row, indexes, visited);
		return count;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int row[] = { 3, 2, 0, 1 };
		System.out.println(new CouplesHoldingHands().minSwapsCouples(row));
	}

}
